LL exgcd(LL a,LL b,LL &x,LL &y)
{
	if(b==0)
	{
		x=1;
		y=0;
		return a;
	}
	LL d=exgcd(b,a%b,x,y);
	LL t=x;
	x=y;
	y=t-a/b*y;
	return d;
}
LL a[MAXN],m[MAXN];
LL CRT()
{
    LL M=m[1],A=a[1],t,d,x,y;
    for(LL i=2;i<=n;i++)
	{
        d=exgcd(M,m[i],x,y);
        if((a[i]-A)%d)return -1;
        x=x*(a[i]-A)/d;
		t=m[i]/d;
		x=(x%t+t)%t;
        A=M*x+A;
		M=M*m[i]/d;
		A%=M;
	}
    A=(A%M+M)%M;
    return A;
}
